package P1线性结构.LeetCode单调队列;

import java.util.ArrayDeque;

public class LeetCode862 {
    public static void main(String[] args) {
        System.out.println(Integer.MAX_VALUE);
    }
    public int shortestSubarray(int[] nums, int k) {
        long[] preSum = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            preSum[i + 1] = nums[i] + preSum[i];
        }
        int len = nums.length + 1;
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < preSum.length; i++) {
            //坑：测试用例数据比较多的话 可能会整型溢出
            long curSum = preSum[i];
            //后者的前缀和-队首的前缀和 >= k 说明这个区间的和是 >=k 的，所以需要删除左边元素
            while (!queue.isEmpty() && curSum - preSum[queue.peekFirst()] >= k) {
                len = Math.min(len, i - queue.pollFirst());
            }
            //前缀和没有改变=>加0 或者 前缀和变小=>加负数 需要忽略删除 数值减小且区间扩大的情况
            //整体而言 得保证一个递增的前缀和序列 这样子=>都是整数 不存在0和负数
            while (!queue.isEmpty() && curSum <= preSum[queue.peekLast()]) {
                queue.pollLast();
            }
            //进队 队列为空 或者 后者比队尾大且区间< k
            queue.offerLast(i);
        }
        return len == nums.length + 1 ? -1 : len;
    }
}
